﻿#if 0
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

//class Solution {
//public:
//    string minWindow(string s, string t) {
//        int num = t.size();
//        std::unordered_map<char, int> nums1;
//        for (const auto& ch : t) {
//            ++nums1[ch];
//        }
//
//        std::string ret;
//        std::unordered_map<char, int> nums2;
//        int left, right, count, size;
//        for (left = 0, right = 0, count = 0, size = s.size(); right < size; ++right) {
//            // 入窗口
//            const char& in = s[right];
//            ++nums2[in];
//            if (nums1.count(in) && nums2[in] <= nums1[in]) ++count;
//
//            // 出窗口
//            while (count > num) {
//                const char& out = s[left];
//                if (nums1.count(out) && nums2[out] <= nums1[out]) --count;
//                ++left;
//            }
//
//            // 判断结果
//            if (count == num) {
//                if (ret == "" || right - left + 1 < ret.size()) {
//                    ret = s.substr(left, right - left + 1);
//                }
//            }
//        }
//
//        right -= 1; // 将right指向s中最后一个字符
//        while (count >= num && left <= right) {
//            const char& out = s[left];
//            if (nums1.count(out) && nums2[out] <= nums1[out]) --count;
//            ++left;
//
//            if (count == num) {
//                ret = s.substr(left, right - left + 1);
//            }
//        }
//
//        return ret;
//    }
//};

class Solution {
public:
	string minWindow(string s, string t) {
		constexpr int SIZE = 'z' - 'A' + 1;
		int hash_table1[SIZE] = {};

		int kinds = 0;
		for (const auto& ch : t) {
			if (hash_table1[ch - 'A']++ == 0) ++kinds;
		}

		int pos = -1, len = INT_MAX;
		for (int left = 0, right = 0, sz = s.size(); right < sz; ++right) {
			// 进窗口
			const char& in = s[right];
			if (--hash_table1[in - 'A'] == 0) --kinds;

			// 更新结果并出窗口
			while (kinds == 0) {
				if (right - left + 1 < len) {
					pos = left;
					len = right - left + 1;
				}

				const char& out = s[left++];
				if (hash_table1[out - 'A']++ == 0) ++kinds;
			}
		}
		return (pos == -1 ? "" : s.substr(pos, len));
	}
};

int main()
{
	cout << Solution().minWindow("ADOBECODEBANC", "ABC") << endl;
	return 0;
}

#endif

#if 0
#include <vector>
#include <span>
#include <iostream>
using namespace std;

//class Solution {
//public:
//    vector<int> searchRange(vector<int>& nums, int target) {
//        std::span<const int> view{ nums };
//        bool found = false;
//
//        int left, right, mid;
//        for (left = 0, right = nums.size() - 1, mid = (right - left) / 2 + left; right >= left; mid = (right - left) / 2 + left) {
//            if (target == view[mid]) {
//                found = true;
//                break;
//            }
//            else if (target > view[mid]) left = mid + 1;
//            else right = mid - 1;
//        }
//
//        if (found) {
//            int left = mid, right = mid;
//            while (left >= 1) {
//                if (view[left] == view[left - 1]) --left;
//            }
//            while (right <= (int)view.size() - 2) {
//                if (view[right] == view[right + 1]) ++right;
//            }
//
//            return { left, right };
//        }
//
//        return { -1, -1 };
//    }
//};

class Solution {
public:
	vector<int> searchRange(vector<int>& nums, int target) {
		std::span<const int> view{ nums };
		int n = view.size();

		vector<int> ret{ -1, -1 };

		// 求左端点
		for (int left = 0, right = n - 1, mid = (right - left) / 2 + left; left <= right; mid = (right - left) / 2 + left) {
			if (view[mid] < target) left = mid + 1;
			else right = mid;

			if (left == right && view[left] == target) {
				ret[0] = left;
				break;
			}
		}

		// 求右端点
		for (int left = 0, right = n - 1, mid = (right - left + 1) / 2 + left; left <= right; mid = (right - left + 1) / 2 + left) {
			if (view[mid] <= target) left = mid;
			else right = mid - 1;

			if (left == right && view[left] == target) {
				ret[1] = right;
				break;
			}
		}

		return ret;
	}
};

int main()
{
	vector<int> vec;
	auto ret = Solution().searchRange(vec, 0);
	for (const auto& element : ret) {
		cout << element << " ";
	}
	cout << endl;
	return 0;
}

#endif

#if 0

#include <span>
#include <vector>
#include <array>
using namespace std;

void test1(const span<const int>& view)
{

}

void test2(span<const int> view)
{

}

int main()
{
	vector<int> vc;
	test1(vc);
	test2(vc);

	auto lower_bound = [](const std::span<const int>& view, int target) {};

	return 0;
}

#endif

#if 0

#include <iostream>
#include <vector>
using namespace std;


//int main()
//{
//    if (2 > 1 and 1 > 0) cout << "yes" << endl;
//    if (2 > 1 or 0 > 1) cout << "0 > 1" << endl;
//    cout << (1 xor 1) << endl;
//    cout << compl 1 << endl;
//
//    return 0;
//}


vector<int> test1() {
	static int i = 0;
	if (i % 2 == 0) return { 1,2,3,i++ };
	else return { 4,5,6,i++ };
}

//const vector<int>& test2() {
//    return { 1,2,3 };
//}

int main() {
	auto&& vec1 = test1();
	const auto& vec2 = test1();
	//auto&& vec3 = test2();
	//const auto& vec4 = test2();

	for (const auto& element : vec1) {
		cout << element << " ";
	}
	cout << endl;

	for (const auto& element : vec2) {
		cout << element << " ";
	}
	cout << endl;

	//for (const auto& element : vec3) {
	//    cout << element << " ";
	//}
	//cout << endl;

	//for (const auto& element : vec4) {
	//    cout << element << " ";
	//}
	//cout << endl;
	return 0;
}

#endif

#if 0
#include <vector>
#include <unordered_map>
#include <iostream>
using namespace std;

class Solution {
public:
	int findMaxLength(vector<int>&& nums) {
		std::unordered_map<int, int> hash; // 前缀和与其对应的最小长度
		hash[0] = 0;
		int ret = 0, sum = 0, len = 1;

		for (const auto& element : nums) {
			sum += (element == 0 ? -1 : 1);
			if (hash.count(sum)) ret = std::max(len - hash[sum], ret);
			//hash[sum] = std::min(len++, hash[sum]);
			hash[sum] = hash.contains(sum) ? std::min(len, hash[sum]) : len;
			++len;
		}

		return ret;
	}
};

int main()
{
	cout << Solution().findMaxLength({ 0,1,0 });
	return 0;
}

#endif

#if 0
#include <vector>
using namespace std;

class Solution {
public:
	vector<vector<int>> matrixBlockSum(vector<vector<int>>&& mat, int k) {
		int m = mat.size(), n = mat[0].size();
		vector<vector<long long>> dp(m + 1, vector<long long>(n + 1));

		for (int i = 1; i <= m; ++i) {
			for (int j = 1; j <= n; ++j) {
				dp[i][j] = mat[i - 1][j - 1] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];
			}
		}

		vector<vector<int>> ret(m, vector<int>(n));
		for (int i = 1; i <= m; ++i) {
			for (int j = 1; j <= n; ++j) {
				// ret[i][j] = pass

				int x1 = std::max(1, i - k);
				int y1 = std::max(1, j - k);
				int x2 = std::min(m, i + k);
				int y2 = std::min(n, j + k);

				ret[i - 1][j - 1] = (int)(dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1]);
			}
		}

		return ret;
	}
};


int main() {
	Solution().matrixBlockSum({ { 1,2,3 }, { 4,5,6 }, { 7,8,9 } }, 1);
	return 0;
}

#endif

#if 0

//#include <iostream>
//using namespace std;
//
//int main() {
//
//    cout << (1 bitand 2) << endl;
//    return 0;
//}

#include <vector>
#include <iostream>
using namespace std;

class Solution {
public:
	long long numberOfRightTriangles(vector<vector<int>>& grid) {
		int row = grid.size(), col = grid[0].size();
		vector<int> row_count(row), col_count(col);

		// 统计每一行1的个数
		for (int i = 0; i < row; ++i) {
			int cnt = 0;
			for (const auto& element : grid[i]) {
				if (element) ++cnt;
			}
			row_count[i] = cnt;
		}

		// 统计每一列1的个数
		for (int j = 0; j < col; ++j) {
			int cnt = 0;
			for (const auto& vec : grid) {
				if (vec[j]) ++cnt;
			}
			col_count[j] = cnt;
		}

		long long ret = 0;
		for (int i = 0; i < row; ++i) {
			for (int j = 0; j < col; ++j) {
				if (grid[i][j]) {
					int row_cnt = row_count[i] ? row_count[i] - 1 : 0;
					int col_cnt = col_count[j] ? col_count[j] - 1 : 0;
					ret += (row_cnt * col_cnt);
				}
			}
		}

		return ret;
	}
};

int main() {
	vector<vector<int>> vec{ {0, 1, 0},{0, 1, 1},{0, 1, 0} };

	cout << Solution().numberOfRightTriangles(vec) << endl;
	return 0;
}

#endif

#if 0
#include <vector>
#include <chrono>
#include <random>
#include <iostream>
#include <span>
using namespace std;

class Solution {
public:
	vector<int> sortArray(vector<int>& nums) {
		quickSort(nums, 0, nums.size() - 1);
		return nums;
	}

private:
	// 随机产生[left, right]中的值
	int getIndex(int left, int right) {
		std::uniform_int_distribution<> distribution(left, right); // 产生的随机数在[left, right]
		return distribution(generator);
	}

	// 将[left, right]之间的数按照升序排列
	void quickSort(std::span<int> nums, int left, int right) {
		if (left >= right) return;

		int l = left - 1, r = right + 1, cur = left;
		int key = nums[getIndex(left, right)];
		while (cur < r) {
			if (nums[cur] < key) std::swap(nums[++l], nums[cur++]);
			else if (nums[cur] == key) ++cur;
			else std::swap(nums[--r], nums[cur]);
		}

		quickSort(nums, left, l);
		quickSort(nums, r, right);
	}

private:
	static std::mt19937_64 generator;
};
std::mt19937_64 Solution::generator(std::chrono::system_clock::now().time_since_epoch().count());

int main() {
	vector<int> vec{ 5,1,1,2,0,0 };
	Solution().sortArray(vec);
	return 0;
}

#endif

#if 0
#include <vector>
#include <queue>
using namespace std;

class Solution {
public:
	vector<int> smallestK(vector<int>& arr, int k) {
		if (0 == k) return {};
		std::priority_queue<int> big_heap(begin(arr), begin(arr) + k);

		for (int i = k, size = arr.size(); i < size; ++i) {
			if (big_heap.top() > arr[i]) {
				big_heap.pop();
				big_heap.push(arr[i]);
			}
		}

		vector<int> ans;
		ans.reserve(k);
		while (!big_heap.empty()) {
			ans.emplace_back(big_heap.top());
			big_heap.pop();
		}

		return ans;
	}
};

int main() {
	vector<int> vec{};
	return 0;
}

// @return 
int test(int i, double d) { return 0; };


#endif

#if 0
#include <vector>
#include <array>
#include <span>
#include <algorithm>
#include <iostream>
using namespace std;

class Solution {
public:
	vector<int> countSmaller(vector<int>& nums) {
		int n = nums.size();
		ret.resize(n);
		indexes.resize(n);
		temp.resize(n);
		temp_indexes.resize(n);

		// 初始化indexes
		for (int i = 0; i < n; ++i) indexes[i] = i;

		_countSmaller(nums, 0, n - 1);
		return ret;
	}

private:
	void _countSmaller(std::span<int> nums, const int left, const int right) {
		if (left >= right) return;

		int mid = left + ((right - left) >> 1);

		_countSmaller(nums, left, mid);
		_countSmaller(nums, mid + 1, right);

		int cur1 = left, cur2 = mid + 1, i = left;
		while (cur1 <= mid && cur2 <= right) { // 排序数组, 降序
			if (nums[cur1] <= nums[cur2]) {
				temp[i] = nums[cur2];
				temp_indexes[i++] = indexes[cur2++];
			}
			else {
				ret[indexes[cur1]] += (right - cur2 + 1);
				temp[i] = nums[cur1];
				temp_indexes[i++] = indexes[cur1++];
			}
		}

		while (cur1 <= mid) {
			temp[i] = nums[cur1];
			temp_indexes[i++] = indexes[cur1++];
		}

		while (cur2 <= right) {
			temp[i] = nums[cur2];
			temp_indexes[i++] = indexes[cur2++];
		}

		for (int i = left; i <= right; ++i) {
			nums[i] = temp[i];
			indexes[i] = temp_indexes[i];
		}
	}

private:
	vector<int> ret;
	vector<int> temp;
	vector<int> indexes;
	vector<int> temp_indexes;
};

int main() {
	vector<int> vec{ 1,2,0 };
	auto ret = Solution().countSmaller(vec);
	for (auto& element : ret) cout << element << endl;
	return 0;
}

#endif

#if 0
//#include <string>
//using namespace std;
//
//class Person {
//public:
//    Person() = default;
//    ~Person() = default;
//
//public:
//    double bonus;
//
//protected:
//    int id;
//
//private:
//    string name;
//};
//
//class Me : public Person {
//public:
//    Me() = default;
//    ~Me() = default;
//public:
//    void test() {
//    }
//};

class Base {
public:
	int publicMember;
protected:
	int protectedMember;
private:
	int privateMember;
};

class Derived : public Base {
public:
	void accessMembers(Base& base, Derived& derived) {
		// 通过对象访问公有成员
		base.publicMember = 1;
		derived.publicMember = 2;

		// 通过作用域解析访问公有成员
		Base::publicMember = 3;
		Derived::publicMember = 4;

		// 通过对象访问受保护的成员（只有在Derived类或其成员中）
		//base.protectedMember = 5;
		derived.protectedMember = 6;

		// 不能从外部访问私有成员
		// base.privateMember = 7; // 错误：privateMember是私有的
		//derived.privateMember = 8; // 错误：privateMember是私有的
	}
};

int main() {
	Base base;
	Derived derived;

	derived.accessMembers(base, derived);
	return 0;
}

#endif

#if 0

//[[nodiscard("测试")]]
//int test() { return 1; }
//
//int main() { test();  return 0; }

//#include <vector>
//#include <iostream>
//using namespace std;
//
//int main() {
//    vector<vector<int>> ans;
//    ans.emplace_back(std::initializer_list{1,2,3});
//    for (auto& vec : ans) {
//        for (auto& item : vec) cout << item << endl;
//    }
//
//    auto a = {1,2};
//    std::initializer_list<int>{ 1,2,3 };
//
//    return 0;
//}

#include <iostream>
#include <vector>
#include <ranges>
#include <algorithm>
using namespace std;

class Solution {
public:
	vector<vector<int>> threeSum(vector<int>& nums) {
		ranges::sort(nums);

		vector<vector<int>> ans;
		for (int size = nums.size(), target_index = size - 1; target_index >= 2; --target_index) {
			int left = 0, right = target_index - 1, target = nums[target_index];

			while (left < right) {
				if (nums[left] + nums[right] < target) {
					++left;
					while (left < right && nums[left] == nums[left - 1]) ++left;
				}
				else if (nums[left] + nums[right] > target) {
					--right;
					while (left < right && nums[right] == nums[right + 1]) --right;
				}
				else {
					ans.push_back({ nums[left], nums[right], target });

					++left;
					while (left < right && nums[left] == nums[left - 1]) ++left;
					--right;
					while (left < right && nums[right] == nums[right + 1]) --right;
				}
			}
		}

		return ans;
	}
};

int main() {
	vector<int> vec{ 0,0,0,0 };
	auto ret = Solution().threeSum(vec);

	for (auto& v : ret) {
		for (auto item : v) {
			cout << item << endl;
		}
	}
	return 0;
}


#endif

#if 0
#include <iostream>
#include <string>
using namespace std;

//class Solution {
//public:
//    int numDecodings(string s) {
//        if ('0' == s[0]) return 0;
//        if (!(stoi(s.substr(0, 2)) >= 1 && stoi(s.substr(0, 2)) <= 26)) return 0;
//
//        return 1 + numDecodings(s.substr(1)) + 1 + numDecodings(s.substr(2));
//    }
//};

class Solution {
public:
	int numDecodings(string s) {
		if (0 == s.size()) return 0;
		if ('0' == s[0]) return 0;
		if (1 == s.size()) return 1;
		//if (!(stoi(s.substr(0, 2)) >= 1 && stoi(s.substr(0, 2)) <= 26)) return 0;
		//if (2 == s.size()) return 1 + numDecodings(s.substr(1));

		//return numDecodings(s.substr(1)) + numDecodings(s.substr(2));

		if (2 == s.size() && (stoi(s.substr(0, 2)) >= 1 && stoi(s.substr(0, 2)) <= 26)) return 1 + numDecodings(s.substr(1));

		int ans = 0;
		ans += numDecodings(s.substr(1));

		if ((stoi(s.substr(0, 2)) >= 1 && stoi(s.substr(0, 2)) <= 26)) ans += numDecodings(s.substr(2));
		return ans;
	}
};

int main() {
	cout << Solution().numDecodings("111111111111111111111111111111111111111111111") << endl;
	return  0;
}

#endif

#if 0
#include <vector>
#include <algorithm>
#include <ranges>
#include <iostream>
using namespace std;

class Solution {
public:
	int minimumAddedInteger(vector<int>& nums1, vector<int>& nums2) {
		ranges::sort(nums1);
		ranges::sort(nums2);

		// 因为nums1中只会删除2个字符，所以nums1真正的最小值一定会在删去字符前的前三个字符当中
		// 我们在这里枚举答案
		// 又因为题目要我们求最小的x，且 x == min(nums2) - min(nums1)，当min(nums1)越大时，x越小，所以我们从第三个开始枚举
		// 然后判断nums2是不是nums1 + x的字串就可以了
		for (int i = 2; i >= 1; --i) {
			int x = nums2[0] - nums1[i];

			int j = 0;
			for (int item : nums1) {
				if ((item + x) == nums2[j] && ++j == nums2.size()) return x;
			}
		}

		// 因为答案一定存在，所以如果后两个不是，就一定是第一个
		return nums2[0] - nums1[0];
	}
};

int main() {
	vector<int> vec1{ 5,5,9,9 };
	vector<int> vec2{ 7,7 };
	cout << Solution().minimumAddedInteger(vec1, vec2) << endl;
	return 0;
}

#endif

#if 0
#include <vector>
#include <ranges>
#include <algorithm>
#include <iostream>
using namespace std;


class Solution {
public:
	int minCostClimbingStairs(vector<int>& cost) {
		int n = cost.size();
		//int dp[n + 1];
		//ranges::generate(cost, []() { return 0; });
		vector<int> dp(n + 1);


		dp[n - 1] = cost[n - 1];

		for (int i = n - 2; i >= 0; --i) {
			dp[i] = std::min(cost[i] + dp[i + 1], cost[i] + dp[i + 2]);
		}

		return std::min(dp[0], dp[1]);
	}
};

int main() {
	vector<int> vec{ 10,15,20 };
	cout << Solution().minCostClimbingStairs(vec) << endl;
	return 0;
}

#endif

#if 0

#include "all.h"

class Solution {
public:
	int numDecodings(string s) {
		if ('0' == s[0]) return 0;
		int n = s.size();
		vector<int> dp(n + 1);
		dp[0] = dp[1] = 1;

		for (int i = 2; i <= n; ++i) {
			// i位置单独解码的情况
			dp[i] += (s[i - 1] == '0' ? 0 : dp[i - 1]);

			// i 和 i - 1一起解码的情况
			dp[i] += ((s[i - 2] == '0' || !(1 <= stoi(s.substr(i - 2, 2)) && stoi(s.substr(i - 2, 2)) <= 26)) ? 0 : dp[i - 2]);
		}

		return dp[n];
	}
};

int main() {
	cout << Solution().numDecodings("123456") << endl;
	return 0;
}

#endif

#if 0

#include "all.h"

class Solution {
public:
	int uniquePaths(int m, int n) {
		return C(m + n - 2, m - 1);
	}

private:
	int C(int n, int m) {
		if (0 == m) return 1;

		return factorial(n) / (factorial(m) * factorial(n - m));
	}

	int factorial(int n) {
		int ret = 1;
		while (n) ret *= n--;

		return ret;
	}
};

int main() {
	cout << Solution().uniquePaths(3, 7) << endl;
	return 0;
}

#endif

#if 0
#include "all.h"

class Solution {
public:
	int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
		int m = obstacleGrid.size(), n = obstacleGrid[0].size();
		vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

		if (1 == obstacleGrid[0][0]) return 0;
		else dp[1][1] = 1;

		for (int i = 1; i <= m; ++i) {
			for (int j = 1; j <= n; ++j) {
				if (1 == obstacleGrid[i - 1][j - 1]) {
					dp[i][j] = 0;
					continue;
				}

				if (1 == i && 1 == j) continue;

				dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
			}
		}

		return dp[m][n];
	}
};

int main()
{
	vector<vector<int>> martrix{ {0,0,0},{0,1,0},{0,0,0} };
	cout << Solution().uniquePathsWithObstacles(martrix) << endl;
	return 0;
}

#endif

#if 0
#include "all.h"

class Solution {
public:
	int minFallingPathSum(vector<vector<int>>& matrix) {
		int m = matrix.size(), n = matrix[0].size();

		vector<vector<int>> dp(m + 1, vector<int>(n + 2, 0));

		for (int i = 1; i <= m; ++i) {
			for (int j = 1; j <= n; ++j) {
				dp[i][j] = matrix[i - 1][j - 1] + std::min({ dp[i - 1][j - 1], dp[i - 1][j], dp[i - 1][j + 1] });
			}
		}

		return *std::min_element(begin(dp[m]) + 1, end(dp[m]) - 1);
	}
};

int main() {
	vector<vector<int>> matrix{ {2,1,3},{6,5,4},{7,8,9} };
	cout << Solution().minFallingPathSum(matrix) << endl;
	return 0;
}

#endif

#if 0

#include "all.h"

class Solution {
public:
	int massage(vector<int>& nums) {
		if (nums.size() == 1) return nums[0];

		int n = nums.size();
		vector<int> dp(n, 0);
		dp[0] = nums[0]; dp[1] = nums[1];
		int max = dp[0];

		for (int i = 2; i < n; ++i) {
			dp[i] = max + nums[i];
			max = std::max(max, dp[i - 1]);
		}

		return std::max(max, dp[n - 1]);
	}
};

int main() {
	vector<int> vec{ 2,1,4,5,3,1,1,3 };
	cout << Solution().massage(vec) << endl;
	return 0;
}

#endif

#if 0
#include "all.h"

int secret(int y, int x) {
	int lower = y - x;
	int upper = y;
}

int main() {
	cout << secret(9112, 22) << endl;
	return 0;
}

#endif

#if 0
#include "all.h"

int main() {
	vector<int> vec{ 1,2,3,4,5,6,7,8,9,0 };
	map<int, int> hash;

	//end = hash.crbegin();

   //for (auto&& [key, value] : hash) {
   //    cout << value << endl;
   //}

   //while (int i = 10, i > 0) {

   //}

   //if (int i = 10; i > 0) {

   //}
	return 0;
}


#endif

#if 0
#include "all.h"
//int main() {
//    cout << thread::hardware_concurrency() << endl;
//    return 0;
//}

int main() {
	std::function loop = []() -> void {
		int i = 0;
		while (true) cout << this_thread::get_id() << " has looped " << ++i << " times!" << endl;
		};
	thread t(loop);

	//t.detach();
	return 0;
}

#endif

#if 0
#include "all.h"

int main() {
	condition_variable cond;
	//cond.wait();
	//cond.wait_for();
	return 0;
}


#endif

#if 0
#include "all.h"

//int main() {
//    //cout << boolalpha;
//    //cout << (1 <= 2) << endl;
//    return 0;
//}

#include <iostream>
#include <thread>
#include <future>
using namespace std;

int main()
{
	//promise<int> pr;
	//thread t1([](promise<int>& p) {
	//    p.set_value_at_thread_exit(100);
	//    this_thread::sleep_for(chrono::seconds(3));
	//    cout << "睡醒了...." << endl;
	//    }, ref(pr));

	//future<int> f = pr.get_future();
	//int value = f.get();
	//cout << "value: " << value << endl;

	//t1.join();
	//return 0;

	std::function<std::size_t(int, int)> add =
		[](int begin, int end) -> std::size_t {
		int ret = 0;
		while (begin <= end) {
			ret += begin;
			++begin;
		}
		return ret;
		}
	;

	future<std::size_t> ret1 = async(add, 1, 100000000);
	size_t ret2 = add(1, 100000000);

	cout << "ret1: " << ret1.get() << endl;
	cout << "ret2: " << ret2 << endl;

	return 0;
}

#endif

#if 0
#include "all.h"

#include <iostream>
#include <utility>

void process(int& x) {
	std::cout << "Processing lvalue: " << x << std::endl;
}

void process(int&& x) {
	std::cout << "Processing rvalue: " << x << std::endl;
}

template<typename T>
void forwarder(T&& arg) {
	process(arg);
}

int main() {
	int a = 5;

	forwarder(a);
	forwarder(10);

	return 0;
}


#endif

#if 0
#include "all.h"

int test() {
	static int i = 1;
	return i++;
}

auto adapter() -> decltype(test()) { return test(); };

int main() {
	cout << adapter() << endl;
	return 0;
}

#endif

#if false
#include "all.h"

/**
 * @brief 简介
 * @param str
 * @param view
 * @param left
 * @param right
 * @param count
 * @return
 */

 /// <summary>
 /// 简介
 /// </summary>
 /// <param name="str"></param>
 /// <param name="view"></param>
 /// <param name="left"></param>
 /// <param name="right"></param>
 /// <param name="count"></param>
 /// <returns></returns>

 /// <summary> 
 /// ccc
 /// </summary>
 /// <param name="str"> lasdf </param>
 /// 
 /// 

 /**
 * @brief jianjie
 * @param str ceshi
 * @return test
 */
string test(string str, std::span<const int> view, int left, int right, size_t count) {

}

class Test {
private:

};


int main() {
	return 0;
}


#endif

#if 0
#include <utility>
#include <string>
#include <iostream>

template<typename T>
void swap(T& t1, T& t2) {
	T temp = std::move(t1);
	t1 = std::move(t2);
	t2 = std::move(temp);
}

struct Obj {
	int i;
	double d;
	std::string str;
};

std::ostream& operator<<(std::ostream& os, const Obj& obj) {
	os << obj.i << " " << obj.d << " " << obj.str << std::endl;
	return os;
}

#include <array>
#include <ranges>
#include <algorithm>
#include <functional>
#include <future>
int main() {
	//Obj obj1{ 10,11.1, "hello" };
	//Obj obj2{ 20, 22.2, "world" };

	//std::cout << "before: " << std::endl;
	//std::cout << obj1 << obj2 << std::endl;

	//swap(obj1, obj2);

	//std::cout << "after: " << std::endl;
	//std::cout << obj1 << obj2 << std::endl;

	std::array<int, 5> arr1{ 1,2,3,4,5 };
	std::array<int, 5> arr2{ 6,7,8,9,10 };

	std::ranges::reverse(arr1);
	std::ranges::for_each(arr1, [](auto& element) { std::cout << element << " "; });
	std::cout << std::endl;

	std::ranges::sort(arr2, std::greater<int>());
	std::ranges::for_each(arr2, [](auto& element) {std::cout << element << " "; });
	std::cout << std::endl;

	//auto ret = std::async(std::bind(std::ranges::sort, std::ref(arr2)));
	std::future<void> ret = std::async([&arr2]() { std::ranges::sort(arr2); });
	ret.wait();
	std::ranges::for_each(arr2, [](auto& element) { std::cout << element << " "; });
	std::cout << std::endl;
	return 0;
}

#endif

#if 0
//#include <functional>
//#include <algorithm>
//
//template<typename RandomAccessIterator, typename Compare>
//void qsort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
//
//int main() {
//	return 0;
//}

#include <iostream>
using namespace std;

template<typename T>
struct Container {
	Container() {
		cout << "Container" << endl;
	}

	Container(std::initializer_list<T> l) {
		for (auto& element : l) {
			cout << element << " ";
		}
		cout << endl;
	}
};

template<>
struct Container<int> {
	Container() {
		cout << "Container<int>" << endl;
	}
};

int main() {
	Container<int> ci;
	Container<double> cd;
	Container<short> c({ 1,2,3,4,5,6,7,8,9,0 });

	return 0;
}

#endif

#if 0
#include "all.h"

#define LEN(X) (sizeof(X) / sizeof(X[0]))

int main() {
	//vector<int> v{35, 1, 53, 7, 2};

	//ranges::sort(v);

	//int cnt = 1;
	////while (next_permutation(v.begin(), v.end())) ++cnt;
	//while (ranges::next_permutation(v).found) ++cnt;

	//cout << cnt << endl;

	int arr[10];
	int len1 = sizeof(arr) / sizeof(int);
	int len2 = LEN(arr);

	cout << len1 << " " << len2 << endl;

	return 0;
}

#endif

#if false
#include <cstdio>
#include <cstring>

int main() {
	char str[] = "abcdef";
	auto ret = strlen(&str[0] + 1);
	printf("%zu\n", ret); // &*(str + 0) + 1 -> str + 1

	return 0;
}

#endif

#if 0
// https://leetcode.cn/problems/maximum-number-that-sum-of-the-prices-is-less-than-or-equal-to-k/
// 数位dp give up
#include "all.h"
class Solution {
public:
	long long findMaximumNumber(long long k, int x) {
		vector<long long> dp(1, 0);
		const int bits = sizeof(k) * 8;

		long long i = 0;
		for (i = 1; ; ++i) {
			int move = x;
			long long cnt = 0;
			while (move <= bits) {
				cnt += ((i >> (move - 1)) & 1);
				move += x;
			}

			// dp[i] = cnt + dp[i - 1];
			dp.emplace_back(cnt + dp[i - 1]);
			if (dp[i] > k) break;
		}

		return i - 1;
	}
};

int main() {
	cout << Solution().findMaximumNumber(9, 1) << endl;
	return 0;
}


#endif

#if false

#include <iostream>
using namespace std;

int main() {
	cout << __builtin_popcount(10) << endl;
}

#endif

#if false

class Date {
public:
	Date(int year, int month, int day)
		: year_(year)
		, month_(month)
		, day_(day)
	{}
private:
	int year_;
	int month_;
	int day_;
};

int main() {
	return 0;
}

#endif

#if false
//#include <iostream>
//#include <type_traits>
//using namespace std;
//
//auto add(auto num1, auto num2) {
//	return num1 + num2;
//}
//
//int main() {
//	cout << add(1, 2) << "\n";
//	cout << add(1.2, 2.5) << "\n";
//	cout << add('c', '\0') << "\n";
//
//	return 0;
//}

#include <limits>
#include <vector>
#include <iostream>
using namespace std;

class Solution {
public:
	double findMaxAverage(vector<int>& nums, int k) {
		double sum = 0, ans = std::numeric_limits<double>::lowest();

		for (int i = 0, n = nums.size(); i < n; ++i) {
			// 进窗口
			sum += nums[i];

			// 如果i < k - 1说明窗口的大小还不足k，可以直接跳过后面的
			if (i < k - 1) continue;

			// 更新结果
			ans = std::max(ans, sum / k);

			// 出窗口，保持窗口大小
			sum -= nums[i - k + 1];
		}

		return ans;
	}
};


int main() {
	vector<int> vc{ -1 };
	cout << Solution().findMaxAverage(vc, 1);

	return 0;
}

#endif

#if false
#include <string>
#include <iostream>
using namespace std;

const char* name = "my name";

int main() {
	cout << name << endl;
	name = "your name";
	cout << name << endl;
	return 0;
}

#endif

#if false
#include <vector>
#include <iostream>
using namespace std;

class Solution {
public:
	int maxTurbulenceSize(vector<int>& arr) {
		int n = arr.size();
		if (n < 3) return n;
		int cnt = 2, ans = cnt;
		char comp;
		if (arr[0] < arr[1]) comp = '<';
		else if (arr[0] > arr[1]) comp = '>';
		else comp = '=';

		for (int i = 2; i < n; ++i) {
			char temp;
			if (arr[i - 1] < arr[i]) temp = '<';
			else if (arr[i - 1] > arr[i]) temp = '>';
			else temp = '=';

			if (('<' == comp && '>' == temp) || ('<' == temp && '>' == comp)) ++cnt;
			else cnt = 0;

			comp = temp;

			ans = std::max(ans, cnt);
		}

		return ans + 1;
	}
};

int main() {
	vector<int> vec{ 9,4,2,10,7,8,8,1,9 };
	cout << Solution().maxTurbulenceSize(vec) << '\n';
	return 0;
}

#endif

#if false
#include <iostream>
#include <compare>
#include <format>
using namespace std;


int main() {
	int n = 0;
	cin >> n;
	if (auto &&ret = n <=> 2; ret >= 0) cout << format("{} >= 2", n) << "\n";
	else cout << format("{} < 2", n);
	

	return 0;
}

#endif

#if false
#include <tuple>
#include <compare>
#include <string>
#include <string_view>
#include <iostream>
using namespace std;

//int main() {
//	int len = 0, ans = 0;
//	auto prev_comp = strong_ordering::greater;
//	std::tie(len, ans) = (0 == prev_comp ? make_tuple(1,1) : make_tuple(2,2));
//	return 0;
//}

int main() {
	string str{ "1234567890" };
	string_view view(str);
	string new_str{ view };

	cout << new_str << "\n";

	return 0;
}

#endif

#if false

#include <span>
#include <vector>
#include <array>
#include <algorithm>
#include <iostream>
#include <ranges>
using namespace std;

int countTheMaxNumber(span<const int> nums) {
	int max = nums[0];
	int ans = 0;

	for (int i : nums) {
		if (i > max) {
			max = i;
			ans = 0;
		}

		if (i == max) ++ans;
	}

	return ans;
}


int main() {
	//cout << countTheMaxNumber(vector<int>{ 1, 2, 3, 4, 5, 5, 5, 5 }) << '\n';
	//cout << countTheMaxNumber(vector<int>{ 2, 2, 2, 2, 2 }) << '\n';

	//array<int, 5> arr{ 2,2,2,2,2 };

	//cout << std::ranges::count(arr, *std::ranges::max_element(arr)) << '\n';

	long long ll = 2LL;
	int i = static_cast<int>(ll);
	return 0;
}

#endif

#if false
#include <string>
#include <vector>
#include <iostream>
using namespace std;

class Solution {
public:
	bool isMatch(string s, string p) {
		int m = s.size(), n = p.size();
		vector<vector<bool>> dp(m + 1, vector<bool>(n + 1)); // s[0 : i] p[0 : j]是否能完美匹配
		dp[0][0] = true;
		for (int i = 2; i <= n; ++i) {
			if ('*' == p[i - 1]) dp[0][i] = true;
		}

		for (int i = 1; i <= m; ++i) {
			for (int j = 1; j <= n; ++j) {
				if ('*' == p[j - 1]) {
					if ('.' == p[j - 2]) dp[i][j] = dp[i][j - 2] || dp[i - 1][j];
					else dp[i][j] = dp[i][j - 2] || (s[i - 1] == p[j - 2] && dp[i - 1][j]);
				}
				else dp[i][j] = (s[i - 1] == p[j - 1] || '.' == p[j - 1]) && dp[i - 1][j - 1];
			}
		}

		return dp[m][n];
	}
};

int main() {
	cout << std::boolalpha << Solution().isMatch("a", ".*..a*") << '\n';
	return 0;
}

#endif

#if false
#include <string>
#include <vector>
#include <iostream>
using namespace std;

class Solution {
public:
	bool isInterleave(string s1, string s2, string s3) {
		int m = s1.size(), n = s2.size();
		if (s3.size() != m + n) return false;

		vector<vector<bool>> dp(m + 1, vector<bool>(n + 1)); // s1[0 : i] 与 s2[0 : j] 能否拼接成 s3[0 : i + j]
		// 预处理
		dp[0][0] = true;
		for (int i = 1; i <= n; ++i) {
			if (s2[i - 1] == s3[i - 1]) dp[0][i] = true;
			else break;
		}
		for (int i = 1; i <= m; ++i) {
			if (s1[i - 1] == s3[i - 1]) dp[i][0] = true;
			else break;
		}

		for (int i = 1; i <= m; ++i) {
			for (int j = 1; j <= n; ++j) {
				if (s1[i - 1] == s3[i + j - 1]) dp[i][j] = dp[i - 1][j];
				else if (s2[j - 1] == s3[i + j - 1]) dp[i][j] = dp[i][j - 1];
			}
		}

		return dp[m][n];
	}
};

int main() {
	cout << Solution().isInterleave("aabc", "abad", "aabadabc") << '\n';
	return 0;
}

#endif

#if true
//#include "all.h"
//
//class Solution {
//public:
//	int minimumDeleteSum(string s1, string s2) {
//		if (s1 == s2) return 0;
//
//		int m = s1.size(), n = s2.size();
//		vector<vector<int>> dp(m + 1, vector<int>(n + 1)); // s1[0:i] s2[0:j]区间内的最小ASCII删除和
//
//		// 预处理第一行
//		for (int j = 1, sum = 0; j <= n; ++j) dp[0][j] = (sum += s2[j - 1]);
//		// 预处理第一列
//		for (int i = 1, sum = 0; i <= m; ++i) dp[i][0] = (sum += s1[i - 1]);
//
//		for (int i = 1; i <= m; ++i) {
//			for (int j = 1; j <= n; ++j) {
//				if (s1[i - 1] == s2[j - 1]) dp[i][j] = dp[i - 1][j - 1];
//				else dp[i][j] = std::min(s1[i - 1] + dp[i - 1][j], s2[j - 1] + dp[i][j - 1]);
//			}
//		}
//
//		return dp[m][n];
//	}
//};
//
//
//int main() {
//	cout << Solution().minimumDeleteSum("delete", "leet") << '\n';
//	return 0;
//}

//auto add(auto a, auto b) { return a + b; }
//
//int main() {
//	auto ret1 = add(1, 2);
//	auto ret2 = add(1.0, 2);
//	return 0;
//}

#endif

#if false
#include <iostream>
#include <format>
#include <string>
using namespace std;

//int main() {
//	/*cout << 0b111 << '\n';*/
//
//	//int mod = ((-9 % 16) + 16) % 16;
//	//cout << mod << endl;
//	//cout << (-3 >> 1) << endl;
//
//	unsigned int i = 0;
//	for (i = 10; i <= 10; --i) cout << i << " ";
//	cout << '\n';
//	return 0;
//}

//union {
//	int i;
//	char ch;
//}un;
//
//void check1() {
//	int a = 1;
//	char ch = *reinterpret_cast<char*>(&a);
//	if (ch == 1) cout << "small" << '\n';
//	else cout << "big" << '\n';
//}
//
//void check2() {
//	un.i = 1;
//	if (un.ch == 1) cout << "small" << '\n';
//	else cout << "big" << '\n';
//}
//
//int main() {
//	check1();
//	check2();
//	return 0;
//}

void print() {
	//int i = 0x12345678;
	//void* p = &i;
	//printf("%p\n", &i);
	//cout << format("{}", p);
	//char* p = (char*)&i;
	//for (int i = 0; i < sizeof(int); ++i, ++p) {
	//	printf("%p, %x\n", p, *p);
	//}


	int i = 0x12345678;
	char* p = (char*)&i;
	int count = sizeof(i);
	while (count-- > 0) {
		cout << format("ptr: {:p}, value: {:X}", static_cast<void*>(p), *p) << '\n';
		++p;
	}
}

int main() {
	//print();
	//cout << -INT_MAX << " " << -INT_MIN << endl;
	/*cout << ((1234 | -1234) >> 31) << endl;*/

	cout << 2 * (-DBL_MAX * 2) << endl;

	return 0;
}

#endif

#if false
#include <iostream>
using namespace std;

//void Xor(int a, int b) {
//	cout << (~((~a) & (~b)) & (~(a & b))) << endl;
//}

//int main() {
//	Xor(123789, 1124689);
//	cout << (123789 xor 1124689) << endl;
//	return 0;
//}

int allOddBits(int x) {
	//x = x ^ 0XAA;
	//x = x ^ (0XAA << 8);
	//x = x ^ (0XAA << 8);
	//x = x ^ (0XAA << 8);

	//x = x ^ 0xaa;
	//x = (x >> 8) ^ 0xaa;
	//x = (x >> 8) ^ 0xaa;
	//x = (x >> 8) ^ 0xaa;

	return !x;
}

int negative(int i) {
	return (~i) + 1;
}

int main() {
	//int ret = ((1 << 31) - 1) ^ INT_MIN;
	//cout << ret << "\n"sv;
	//cout << 0xAAAAAAAA << '\n';
	cout << allOddBits(0xaaaaaaaa) << '\n';
	//cout << negative(1) << endl;
	//cout << negative(-2) << endl;
	return 0;
}

#endif

#if 0
//#include <iostream>
//using namespace std;
#include <stdio.h>
#include <stdlib.h>
//int main() {
//	int a, b;
//	cin >> a >> b;
//
//	int c = a + b;
//
//	cout << c << '\n';
//
//	return 0;
//}


//int main() {
//	std::boolalpha(cout);
//	cout << (abs(INT_MIN) == INT_MIN) << '\n';
//	return 0;
//}

int a = 10;
int b;

void test() {}

int main() {
	//int&& i = 1;
	const char* str = "123456";
	int temp = 100;
	//int* p = new int(3);
	int* p = (int*)malloc(sizeof(int));
	printf("%p\n", str);
	printf("%p\n", test);
	printf("%p\n", &a);
	printf("%p\n", &b);
	printf("%p\n", &temp);
	printf("%p\n", p);

	free(p);

	return 0;
}

#endif

#if true
#include <iostream>
#include <format>
using namespace std;


int main() {
	int array1[10];
	int array2[10];

	cout << format("array1: {:p}, &array1[0]: {:p}, &array1[1]: {:p}", (void*)array1, (void*)&array1[0], (void*)&array1[1]) << '\n';
	cout << format("array2: {:p}, &array2[0]: {:p}, &array2[1]: {:p}", (void*)array2, (void*)&array2[0], (void*)&array2[1]) << '\n';
	return 0;
}

#endif